
[STAR.REC]

[move head back and forth until the nearest * is found]

[Q0 looks for an initial star, halts or shifts right]
[Q1 looks for an immediate star, halts or places the right marker]
[Q2 places the left marker, halt is illusory]
[Q3 runs right until it finds the right fence]
[Q4 extends the right fence, bounces]
[Q5 erases the left marker]
[Q6 extends the left fence, bounces]
[Q7 erases the right marker]
[Q8 runs left and halts over the star]
[Q9 runs left until it finds the left fence]
[Q10 runs right and halts over the star]

[A Turing machine has a very limited scope of vision, but it can
 use as many states as necessary to remember what it is running 
 back and forth looking for. It can also use up as much tape as it
 wants to record intermediate results, but at the price of placing
 markers to identify the information or using more states to recall
 where it was deposited.]

[It is well known that a Turing machine obtains results through an
 incredibly complicated series of movements; its principal reason
 for existence is that the simplicity of its definition and oper-
 ation permits theorems to be proven about its operation or non-
 operation, which then apply to any other computation, according
 to Church's thesis.]

[It is quite instructive to set up the generally used programming
 concepts, such as the use of veriables, the introduction of
 subroutines, and even structured programming, in terms of the
 set theory of the state space of a Turing machine. The tradeoff
 between the number of symbols on the tape and the number of states
 in the machine can be studied experimentally, as well as most of
 the other traditional results of Turing machine theory, ending
 with the construction of a Universal machine.]

[[]]

{
  [head right]			(AAB;'.'I;;)+
  [head left]			(B;'.'I;;)-
  [head stationary]		(;)0
  [test equality]		(pGm=n;nL)=
  [cr.lf]			(2573TL;)&
  [read phrase]			(R13%='';T08%(=2080[sp,bs]TL)(@J|;L@J;);)J
  [sign-on message]		('
This Turing machine seeks the nearest "1" on its tape.
Type the initial tape, using * for 1, . for 0, but be sure
to place a # in front of the bit which is under the reading
head. End the tape with a carriage return.  For example -

            ....*........#........

Each succeeding keystroke will display one step of the
Turing machine`s operation, showing a segment of the tape
followed by the state which produced the line shown.
'TL@&'Initial Tape:'TL@&@JI'#'FD;:)R
  [write tape segment]		(j(20b;J;)qtz' 'TABqtTLz(20a;LZ;)qtB;) W
				(@R'Q0'(@&@WRLT

[* at once, quit]		('Q0'@='*'E;)D'*'IL'H'@0:
[go right, look there]		('Q0'@='.'E;)D'.'IL'Q1'@+:
[found it]			('Q1'@='*'E;)D'*'IL'H'@0:
[make right fence, go left]	('Q1'@='.'E;)D'*'IL'Q2'@-:
[this won't happen]		('Q2'@='*'E;)D'*'IL'H'@0:
[set left fence, go right]	('Q2'@='.'E;)D'*'IL'Q3'@+:
[erase fence, look beyond]	('Q3'@='*'E;)D'.'IL'Q4'@+:
[keep looking for fence]	('Q3'@='.'E;)D'.'IL'Q3'@+:
[found *, go erase l fence]	('Q4'@='*'E;)D'*'IL'Q9'@-:
[set in new fence, go left]	('Q4'@='.'E;)D'*'IL'Q5'@-:
[erase fence, look beyond]	('Q5'@='*'E;)D'.'IL'Q6'@-:
[keep heading left]		('Q5'@='.'E;)D'.'IL'Q5'@-:
[found *, go erase r fence]	('Q6'@='*'E;)D'*'IL'Q7'@+:
[set in new fence, go right]	('Q6'@='.'E;)D'*'IL'Q3'@+:
[found fence, go left to *]	('Q7'@='*'E;)D'.'IL'Q8'@-:
[keep looking for fence]	('Q7'@='.'E;)D'.'IL'Q7'@+:
[here's * we're looking for]	('Q8'@='*'E;)D'*'IL'H'@0:
[keep on looking left]		('Q8'@='.'E;)D'.'IL'Q8'@-:
[found fence, go right to *]	('Q9'@='*'E;)D'.'IL'Q10'@+:
[keep looking for fence]	('Q9'@='.'E;)D'.'IL'Q9'@-:
[here's * we're looking for]	('Q10'@='*'E;)D'*'IL'H'@0:
[continue rightward search]	('Q10'@='.'E;)D'.'IL'Q10'@+:
'H'=;);)}

[end]
